package leetcode.hot100;

import leetcode.tester.Tester;

import java.io.IOException;

/**
 * 283. 移动零
 * https://leetcode.cn/problems/move-zeroes/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author Liu Yicong
 * @date 2025/10/11
 */
public class Hot4DbpMoveZeroes {
	public static void main(String[] args) throws IOException {
		Object[][] inputs = {
				new Object[]{new int[]{0, 1, 0, 3, 12},},
				new Object[]{new int[]{0},},
				new Object[]{new int[]{0, 0},},
		};
		Object[] outputs = {
				new int[]{1, 3, 12, 0, 0},
				new int[]{0},
				new int[]{0, 0},
		};
		Tester.test(Tester.wrap(new Hot4DbpMoveZeroes()::moveZeroes), inputs, outputs);
		Tester.test(Tester.wrap(new Hot4DbpMoveZeroes()::moveZeroesOpt), inputs, outputs);

	}

	/**
	 * 使用双指针逐个交换元素的方式
	 */
	private int[] moveZeroes(int[] nums) {
		int n = nums.length;
		if (n == 1) {
			return nums;
		}
		// 定义两个指针，l用来遍历元素，r则寻找l之后的非0元素
		int l = 0, r = 1;
		while (l < n && r < n) {
			// 如果指针l指向的元素不为0
			if (nums[l] != 0) {
				l++;
				r++;
			}
			// 如果指针l指向的元素为0
			else {
				// r指针向后寻找不为0的元素, 并与l指针的元素进行交换
				while (r < n - 1 && nums[r] == 0) {
					r++;
				}
				int temp = nums[l];
				nums[l] = nums[r];
				nums[r] = temp;
				l++;
			}
		}
		return nums;
	}

	/**
	 * 将不为0的元素依次排列，并记录个数，最后在数组的尾部全部置为0
	 */
	private int[] moveZeroesOpt(int[] nums) {
		int stackSize = 0;
		for (int x : nums) {
			if (x != 0) {
				nums[stackSize] = x;
				stackSize++;
			}
		}
		for (int i = stackSize; i < nums.length; i++) {
			nums[i] = 0;
		}
		return nums;
	}
}
